/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/implement-strstr
   @Language: C++
   @Datetime: 16-02-09 09:42
   */

// Method 1, using string.find()
class Solution {
public:
	/**
	 * @param source: 
	 * @param target: 
	 * @return: return the index
	 */
	int strStr(string &source, string &target) {
		// Write your code here
		return source.find(target);
	}
};

// Method 2, using KMP
class Solution {
	void getnext(string &target, vector<int> &next){
		int lt=target.length();
		for(int i=0, j=-1; i<lt;){
			if(j==-1 || target[i]==target[j]){
				++i, ++j;
				next[i]=(target[i]==target[j]?next[j]:j);
			}
			else j=next[j];
		}
	}
public:
	/**
	 * Returns a index to the first occurrence of target in source,
	 * or -1  if target is not part of source.
	 * @param source string to be scanned.
	 * @param target string containing the sequence of characters to match.
	 */
	/** Tips: The classical KMP and optimize the next[]
	 * Source String: a b a c a a b a c a b a a b b
	 * Target String: a b a c a b
	 * using index i refers to S, j refers to T, begin from 0
	 * when match the 5th char, S is 'a' otherwise T is 'b',
	 * traditional method is to rematch from 1th char 'b' (i=1,j=0)
	 *
	 * Why don't match current next : i=6,j=0?
	 * Because the S[2] equal to T[0], may match the T. And Why? 
	 * Because the T has same char such as 'a', 'b'.
	 *
	 * If the T is "abcdef", S is "abcdekabcd": match the 5th failure,
	 * We don't need remove the i to range [0,4], 
	 * just match next : i=6, and j=0
	 *
	 * So, KMP idea do process for Target, and calculate that
	 * when match failure, the next match refers to where.
	 *
	 * I'll write a note for KMP details later.
	 * */
	int strStr(string &source, string &target) {
		// write your code here
		int ls=source.length(), lt=target.length();
		vector<int> next(lt+1,-1);
		getnext(target,next);
		int i=0, j=0;
		while(i<ls && j<lt){
			if(j==-1 || source[i]==target[j]) ++i, ++j;
			else j=next[j];
		}
		return j==lt?i-lt:-1;
	}
};
